//
// Created by f12160c on 2018/7/25.
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <list>

#include "leetcode/leetcode.hpp"

using namespace std;

struct board_info {
public:
    struct alternative;
    struct unfinished_list{
        alternative *self;
        unfinished_list *prev;
        unfinished_list *next;
    };
    struct alternative {
        list<int> val;
        int r, c;
        unfinished_list row;
        unfinished_list col;
        unfinished_list cell;
    };
    alternative alternatives[9][9];

    unfinished_list solved;
    unfinished_list rows[9];
    unfinished_list cols[9];
    unfinished_list cells[9];

    int raws_state[9][9];
    int cols_state[9][9];
    int cells_state[9][9];
    int unsolved_count;

    board_info(const vector<vector<char>> &board){
        int k, tmp;
        alternative *pAlt;
        list<int> *pVal;
        unsolved_count = 81;
        for(int i = 0; i < 9; i++){
            rows[i].prev = rows[i].next = &rows[i];
            cols[i].prev = cols[i].next = &cols[i];
            cells[i].prev = cells[i].next = &cells[i];
            for(int j = 0; j < 9; j++){
                raws_state[i][j] = 9;
                cols_state[i][j] = 9;
                cells_state[i][j] = 9;
            }
        }
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                pAlt = &alternatives[i][j];
                pVal = &pAlt->val;
                if(board[i][j] == '.'){
                    k = i/3*3+j/3;
                    pAlt->r = i;
                    pAlt->c = j;

                    for(int m = 0; m < 9; m++){
                        pVal->push_back(m);
                    }
                    pAlt->row.self = pAlt;
                    pAlt->col.self = pAlt;
                    pAlt->cell.self = pAlt;
                    unfinished_list_add(&rows[i], &pAlt->row);
                    unfinished_list_add(&cols[j], &pAlt->col);
                    unfinished_list_add(&cells[k], &pAlt->cell);
                } else {
                    tmp = board[i][j] - '1';
                    pVal->push_back(tmp);
                    mark_solved(i, j, tmp);
                }
            }
        }
        solved.prev = solved.next = &solved;
    }

    board_info(const board_info & old){
        const unfinished_list *pTmp, *pHead;
        alternative *pAlt, *pOldAlt;

        for(int i = 0; i < 9; i++) {
            rows[i].prev = rows[i].next = &rows[i];
            cols[i].prev = cols[i].next = &cols[i];
            cells[i].prev = cells[i].next = &cells[i];
        }
        for(int i = 0; i < 9; i++){
            pTmp = pHead = &old.rows[i];
            while(pTmp->next != pHead){
                pOldAlt = pTmp->next->self;
                pAlt = &alternatives[pOldAlt->r][pOldAlt->c];
                pAlt->val = pOldAlt->val;
                pAlt->r = pOldAlt->r;
                pAlt->c = pOldAlt->c;
                pAlt->row.self = pAlt;
                pAlt->col.self = pAlt;
                pAlt->cell.self = pAlt;
                unfinished_list_add(&rows[pOldAlt->r], &pAlt->row);
                unfinished_list_add(&cols[pOldAlt->c], &pAlt->col);
                unfinished_list_add(&cells[pOldAlt->r/3*3+pOldAlt->c/3], &pAlt->cell);

                pTmp = pTmp->next;
            }
        }
        memcpy(&raws_state, &old.raws_state, sizeof(raws_state));
        memcpy(&cols_state, &old.cols_state, sizeof(cols_state));
        memcpy(&cells_state, &old.cells_state, sizeof(cells_state));
        unsolved_count = old.unsolved_count;
    }

    board_info &operator= (const board_info & old) = delete;

    bool solve_try(int row, int col, int val){
        auto pAlt = &alternatives[row][col];
        pAlt->val.clear();
        pAlt->val.push_back(val);
        pAlt->row.prev->next = pAlt->row.next;
        pAlt->row.next->prev = pAlt->row.prev;
        pAlt->col.prev->next = pAlt->col.next;
        pAlt->col.next->prev = pAlt->col.prev;
        pAlt->cell.prev->next = pAlt->cell.next;
        pAlt->cell.next->prev = pAlt->cell.prev;
        unfinished_list_add(&solved, &pAlt->row);
        if(!clear_sovled()){
            return false;
        }
        if(unsolved_count){
            if(!solve_enhance()){
                return false;
            }
        }
        return solve_recursive();
    }

    bool solve_recursive(void){
        const unfinished_list *pTmp, *pHead;
        alternative *pAlt;
        int min_count = 10;
        int curr_count;
        alternative *pMinAlt;
        for(int i = 0; i < 9; i++) {
            pTmp = pHead = &rows[i];
            while(pTmp->next != pHead){
                pAlt = pTmp->next->self;
                curr_count = pAlt->val.size();
                if(min_count > curr_count){
                    pMinAlt = pAlt;
                    if(curr_count == 2){
                        goto try_alt;
                    }
                    min_count = curr_count;
                }
                pTmp = pTmp->next;
            }
        }
        try_alt:
        for(auto &v: pMinAlt->val) {
            board_info info_try(*this);
            if (info_try.solve_try(pMinAlt->r, pMinAlt->c, v)) {
                for (int i = 0; i < 9; i++) {
                    pTmp = pHead = &rows[i];
                    while (pTmp->next != pHead) {
                        pAlt = pTmp->next->self;
                        pAlt->val = info_try.alternatives[pAlt->c][pAlt->c].val;
                        pTmp = pTmp->next;
                    }
                }
                unsolved_count = 0;
                return true;
            }
        }
        return false;
    }

    bool solve(void){
        if(!solve_base()){
            return false;
        }
        if(unsolved_count){
            if(!solve_enhance()){
                return false;
            }
        }
        if(unsolved_count){
            return solve_recursive();
        }
        return false;
    }

    void build_output(vector<vector<char>> &board){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == '.'){
                    list<int> &val = alternatives[i][j].val;
                    if(val.size() == 1) {
                        cout << val.front() + 1 << "        ";
                        board[i][j] = val.front() + '1';
                    } else if (val.size() == 0){
                        throw "value error";
                    } else {
                        if(true) {
                            for (auto &c: val) {
                                cout << c + 1;
                            }
                            for (int i = val.size(); i < 9; i++) {
                                cout << " ";
                            }
                        } else {
                            cout << ".        ";
                        }
                    }
                } else {
                    cout << board[i][j] - '0' << "        ";
                }
            }
            cout << endl;
        }
    }

private:
    inline void unfinished_list_add(unfinished_list *pHead, unfinished_list *elm){
        elm->prev = pHead->prev; elm->next = pHead; pHead->prev->next = elm; pHead->prev = elm;
    }

    inline bool mark_solved(int i, int j, int val){
        int k = i/3*3+j/3;
        if((raws_state[i][val] == val) || (cols_state[j][val] == val) || (cells_state[k][val] == val)) {
            return false;
        }
        raws_state[i][val] = val;
        cols_state[j][val] = val;
        cells_state[k][val] = val;
        unsolved_count--;
        return true;
    }

    inline bool clear_sovled(void){
        unfinished_list *pTmpSolvedHead;
        unfinished_list *pTmpSolved;
        alternative *pAlt;
        int v;
        bool ret = true;

        pTmpSolved = pTmpSolvedHead = &solved;
        while(pTmpSolved->next != pTmpSolvedHead) {
            pAlt = pTmpSolved->next->self;
            v = pAlt->val.front();
            scan_and_remove(&rows[pAlt->r], v);
            scan_and_remove(&cols[pAlt->c], v);
            scan_and_remove(&cells[pAlt->r/3*3 + pAlt->c/3], v);
            if(!mark_solved(pAlt->r, pAlt->c, v)){
                ret = false;
                break;
            }
            pTmpSolved = pTmpSolved->next;
        }
        solved.prev = solved.next = &solved;
        return ret;
    }

    inline void scan_and_remove(unfinished_list *pHead, int val) {
        unfinished_list *pTmpHead = pHead;
        alternative *pAlt;
        while (pTmpHead->next != pHead) {
            pAlt = pTmpHead->next->self;
            pAlt->val.remove(val);
            if (pAlt->val.size() == 1) {
                pAlt->row.prev->next = pAlt->row.next;
                pAlt->row.next->prev = pAlt->row.prev;
                pAlt->col.prev->next = pAlt->col.next;
                pAlt->col.next->prev = pAlt->col.prev;
                pAlt->cell.prev->next = pAlt->cell.next;
                pAlt->cell.next->prev = pAlt->cell.prev;
                unfinished_list_add(&solved, &pAlt->row);
            } else {
                pTmpHead = pTmpHead->next;
            }
        }
    }

    inline bool check_hidden_and_remove(unfinished_list *pHead) {
        unfinished_list  *val_ptr[9];
        int val_count[9];
        unfinished_list *pTmpHead = pHead;
        alternative *pAlt;

        if(pTmpHead->next == pHead){
            return false;
        }

        for(int i = 0; i < 9; i++){
            val_count[i] = 0;
        }

        while(pTmpHead->next != pHead){
            list<int> &val = pTmpHead->next->self->val;
            for(auto &v: val){
                val_count[v]++;
                val_ptr[v] = pTmpHead;
            }
            pTmpHead = pTmpHead->next;
        }

        for(int i = 0; i < 9; i++){
            if(val_count[i] == 1){
                pAlt = val_ptr[i]->next->self;
                pAlt->val.clear();
                pAlt->val.push_back(i);
                pAlt->row.prev->next = pAlt->row.next;
                pAlt->row.next->prev = pAlt->row.prev;
                pAlt->col.prev->next = pAlt->col.next;
                pAlt->col.next->prev = pAlt->col.prev;
                pAlt->cell.prev->next = pAlt->cell.next;
                pAlt->cell.next->prev = pAlt->cell.prev;
                unfinished_list_add(&solved, &pAlt->row);
                return true;
            }
        }
        return false;
    }

    bool solve_enhance(void){
        bool ret = true;
        loop:
        for(int i = 0; i < 9; i++){
            if(check_hidden_and_remove(&rows[i])
               || check_hidden_and_remove(&cols[i])
               || check_hidden_and_remove(&cells[i])){
                if(!clear_sovled()){
                    ret = false;
                    break;
                }
                if(unsolved_count){
                    goto loop;
                }
            }
        }
        return ret;
    }

    bool solve_base(void){
        alternative *pAlt;
        int v;
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                pAlt = &alternatives[i][j];
                if(pAlt->val.size() == 1){
                    v = pAlt->val.front();
                    scan_and_remove(&rows[i], v);
                    scan_and_remove(&cols[j], v);
                    scan_and_remove(&cells[i/3*3 + j/3], v);
                }
            }
        }
        return clear_sovled();
    }
};


void Solution::solveSudoku(vector<vector<char>>& board) {
    board_info info(static_cast<const vector<vector<char >>>(board));
    info.solve();
    info.build_output(board);
}